import java.util.HashMap;

class MinWindow {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";

        int minLength = 1 << 16;
        int start_pos = -1;
        int end_pos = -1;

        HashMap<Integer, HashMap<Character, Integer>> smap = new HashMap<>();
        HashMap<Character, Integer> tmap = new HashMap<>();
        
        for (int i=0; i<t.length(); ++i){
            char c  = t.charAt(i);
            if(tmap.containsKey(c)) {
                tmap.replace(c, tmap.get(c) + 1);
            } else {
                tmap.put(c, 1);
            }
        }
        // System.out.println(tmap.toString());

        HashMap<Character, Integer> counter = new HashMap<Character, Integer>();
        for (char c: tmap.keySet()){
            counter.put(c, 0);
        }
        for (int i=0; i<s.length(); ++i){
            char c  = s.charAt(i);
            if (tmap.containsKey(c)){
                counter.replace(c, counter.get(c) + 1);
                HashMap<Character, Integer> clone = new HashMap<>();
                clone.putAll(counter);
                smap.put(i, clone);
            }
        }
        // System.out.println(smap.toString());

        for (int left=0; left<s.length(); ++left){
            char c = s.charAt(left);
            if (tmap.containsKey(c)) {
                HashMap<Character, Integer> leftMap = smap.get(left);
                for (int right = s.length()-1; right >= left; --right){
                    char rc = s.charAt(right);
                    if (tmap.containsKey(rc)){
                        HashMap<Character, Integer> rightMap = smap.get(right);
                        HashMap<Character, Integer> tmp = new HashMap<Character, Integer>();
                        for (char key: rightMap.keySet()){
                            tmp.put(key, rightMap.get(key) - leftMap.get(key));
                        }
                        tmp.replace(c, tmp.get(c) + 1);

                        // System.out.println(rightMap);
                        // System.out.println(leftMap);
                        // System.out.println(tmp);
                        // System.out.println();

                        boolean flag = false;
                        for (char key: tmap.keySet()){
                            if (!tmp.containsKey(key) || tmp.get(key) < tmap.get(key)){
                                flag = true;
                                break;
                            }
                        }
                        if(flag) break;
                        else{
                            int length = right - left + 1;
                            if (length < minLength){
                                minLength = length;
                                start_pos = left;
                                end_pos = right;
                            }
                        }
                    }
                }
            }
        }

        if (start_pos == -1 || end_pos == -1){
            return "";
        }

        StringBuilder builder = new StringBuilder();
        for (int i=start_pos; i<=end_pos; ++i){
            builder.append(s.charAt(i));
        }
        return builder.toString();
    }

    public static void main(String[] args){
        MinWindow s = new MinWindow();
        String S = "ADOBECODEBANC", T = "ABC";
        // String S = "aa", T = "aa";
        String res = s.minWindow(S, T);
        System.out.println(res);
    }
}